package kyssion.leetcode.num51_100;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 给出一个区间的集合，请合并所有重叠的区间。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2:
 * <p>
 * 输入: [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */
public class code56_合并区间 {

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new code56_合并区间().merge(
                new int[][]{
                        {1, 1},
                        {1, 2},
                        {1, 3},
                        {1, 4},
                        {1, 5},
                        {1, 6},
                }
        )));
    }

    public int[][] merge(int[][] intervals) {

        if (intervals.length == 0 || intervals[0].length != 2) {
            return intervals;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0]) {
                    return -1;
                } else if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return 1;
                }
            }
        });

        int index = 0;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int a = 0; a < intervals.length; a++) {
            if (intervals[a][0] <= right && intervals[a][1] > right) {
                right = intervals[a][1];
            } else if (intervals[a][0] > right) {
                intervals[index][0] = left;
                intervals[index][1] = right;
                left = intervals[a][0];
                right = intervals[a][1];
                index++;
            }
        }
        intervals[index][0] = left;
        intervals[index][1] = right;
        int[][] item = new int[index + 1][2];
        for (int a = 0; a <= index; a++) {
            item[a][0] = intervals[a][0];
            item[a][1] = intervals[a][1];
        }
        return item;
    }

    /**
     * 这里记一下思路吧,就是把所有的左边和右边全部都压平到一个数轴上
     * 然后只要定义一个边界就行了,如果左侧的边界超过了右侧的边界,就表示这个闭环已经形成了
     * @param intervals
     * @return
     */
    public int[][] merge2(int[][] intervals) {
        int m = intervals.length;
        if (m == 0 || m == 1)
            return intervals;
        int[][] temp = new int[m][2];
        // 分别将左右区间拿出来，进行排序
        int[] left = new int[m];
        int[] right = new int[m];
        for (int i = 0; i < intervals.length; i++) {
            left[i] = intervals[i][0];
            right[i] = intervals[i][1];
        }
        Arrays.sort(left);
        Arrays.sort(right);
        int pre = 0;


        for (int i = 0, j = 0; i < m; i++) {
            if (i == m - 1 || left[i + 1] > right[i]) {
                temp[pre][0] = left[j];
                temp[pre][1] = right[i];
                pre++;
                // 不能用j++，因为当从合并区间出来之后用非合并的区间时，j要恢复到与i对应的值
                j = i + 1;
            }
        }
        int[][] ans = new int[pre][2];
        for (int i = 0; i < pre; i++) {
            ans[i][0] = temp[i][0];
            ans[i][1] = temp[i][1];
        }
        return ans;
    }
}
